Cable TV systems often include a channel dedicated to displaying listings of programs available on the different available channels. The listings are commonly arranged in a grid. Each column of the grid represents a particular time slot, such as 4:00 p.m. to 4:30 p.m. Each row represents a particular broadcast or cable channel, such as ABC, PBS, or ESPN. The various scheduled programs or shows are arranged within the rows and columns, indicating the channels and times at which they can be found. The grid is continuously scrolled vertically so that a viewer can scan a number of different channels within three or four time slots.
Data regarding available programs is typically received by a cable system as a plurality of data records. Each available program has a single corresponding data record indicating a variety of information about the program such as its channel, its starting and ending times, its title, names of starring actors, whether closed-captioning and stereo are available, and perhaps a brief description of the program. It is not difficult to format a grid such as described above from this type of data records. The grid is typically formatted once at the cable system's headend and broadcast repeatedly and continuously to the thousands of homes served by the cable system.
Newer, interactive cable distribution systems feature electronic program guides (EPGs) which result in a functionality somewhat similar to the broadcast program listing channels described above. Rather than scrolling automatically, however, an EPG allows a viewer to use a remote control device to scroll as desired both horizontally and vertically through a program grid. This functionality utilizes the two-way communications capabilities of interactive cable systems.
An EPG runs on a user interface device, also referred to as a set-top box (STB), connected in a viewer's home between a TV and a cable system home entry line. When scrolling to a new column or row, the set-top box requests new information from the cable system's headend regarding the programming information which needs to be presented for the new row or column. For instance, when scrolling to a new column, programs falling within a new time slot need to be displayed. The STB requests new information from the cable headend regarding programs available on the displayed channels falling within the new time slot.
The cable headend must be able to process such requests very quickly so that the viewer sees no significant delay. However, determining which data records refer to programs occupying a given time slot is not a trivial task. Even though data records might be arranged chronologically by starting times, it is not sufficient just to search for those records having starting times matching the starting time of the time slot. For example, when using half-hour time slots many programs align perfectly along time slot boundaries. A show starting at 4:00 p.m. and ending at 4:30 p.m. would align perfectly with the 4:00 p.m. to 4:30 p.m. time slot. Other shows, however, might start before the time slot or end after the time slot. Still other shows might begin and end completely within the time slot. Generally, it can only be said that each program will correspond to a scheduled time period and that the scheduled time period of an individual program will occupy at least a portion of one or more of the discrete time slots.
Accordingly, it is necessary to assume a maximum program duration, calculate the earliest possible time a program of the maximum duration might have started while still ending after the start time of the time slot, and then examine all data records representing programs starting between that earliest possible time and the ending time of the time slot. In light of the fact that the maximum program duration might be eight hours or more, such a search involves a great number of records. Furthermore, it must be carried out quite often for every subscriber connected to the cable headend using an EPG. In a typical system, 50,000 to over 250,000 viewers might be connected to a headend. It is apparent that the present configuration and search strategies described above are not satisfactory for a demand of this magnitude.